/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    Rule.java
 *    Copyright (C) 2003 Peter A. Flach, Nicolas Lachiche
 *
 *    Thanks to Amelie Deltour for porting the original C code to Java
 *    and integrating it into Weka.
 */

package weka.associations.tertius;

import weka.core.Instance;
import weka.core.Instances;
import weka.core.RevisionHandler;
import weka.core.RevisionUtils;

import java.io.Serializable;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Enumeration;

/**
 * Class representing a rule with a body and a head.
 * 
 * @author <a href="mailto:adeltour@netcourrier.com">Amelie Deltour</a>
 * @version $Revision: 1.7 $
 */

public class Rule implements Serializable, Cloneable, RevisionHandler {

	/** for serialization */
	private static final long serialVersionUID = -7763378359090435505L;

	/** The body of the rule. */
	private Body m_body;

	/** The head of the rule. */
	private Head m_head;

	/** Can repeat predicates in the rule ? */
	private boolean m_repeatPredicate;

	/** Maximal number of literals in the rule. */
	private int m_maxLiterals;

	/** Can there be negations in the body ? */
	private boolean m_negBody;

	/** Can there be negations in the head ? */
	private boolean m_negHead;

	/** Is this rule a classification rule ? */
	private boolean m_classRule;

	/** Can there be only one literal in the head ? */
	private boolean m_singleHead;

	/** Number of instances in the data this rule deals with. */
	private int m_numInstances;

	/** Set of counter-instances of this rule. */
	private ArrayList m_counterInstances;

	/** Counter for the counter-instances of this rule. */
	private int m_counter;

	/** Confirmation of this rule. */
	private double m_confirmation;

	/** Optimistic estimate of this rule. */
	private double m_optimistic;

	/**
	 * Constructor for a rule when the counter-instances are not stored, giving
	 * all the constraints applied to this rule.
	 * 
	 * @param repeatPredicate
	 *            True if predicates can be repeated.
	 * @param maxLiterals
	 *            Maximum number of literals.
	 * @param negBody
	 *            True if negation is allowed in the body.
	 * @param negHead
	 *            True if negation is allowed in the head.
	 * @param classRule
	 *            True if the rule is a classification rule.
	 * @param horn
	 *            True if the rule is a horn clause.
	 */
	public Rule(boolean repeatPredicate, int maxLiterals, boolean negBody,
			boolean negHead, boolean classRule, boolean horn) {

		m_body = new Body();
		m_head = new Head();
		m_repeatPredicate = repeatPredicate;
		m_maxLiterals = maxLiterals;
		m_negBody = negBody && !horn;
		m_negHead = negHead && !horn;
		m_classRule = classRule;
		m_singleHead = classRule || horn;
	}

	/**
	 * Constructor for a rule when the counter-instances are stored, giving all
	 * the constraints applied to this rule. The counter-instances are
	 * initialized to all the instances in the dataset.
	 * 
	 * @param instances
	 *            The dataset.
	 * @param repeatPredicate
	 *            True if predicates can be repeated.
	 * @param maxLiterals
	 *            Maximum number of literals.
	 * @param negBody
	 *            True if negation is allowed in the body.
	 * @param negHead
	 *            True if negation is allowed in the head.
	 * @param classRule
	 *            True if the rule is a classification rule.
	 * @param horn
	 *            True if the rule is a horn clause.
	 */
	public Rule(Instances instances, boolean repeatPredicate, int maxLiterals,
			boolean negBody, boolean negHead, boolean classRule, boolean horn) {

		m_body = new Body(instances);
		m_head = new Head(instances);
		m_repeatPredicate = repeatPredicate;
		m_maxLiterals = maxLiterals;
		m_negBody = negBody && !horn;
		m_negHead = negHead && !horn;
		m_classRule = classRule;
		m_singleHead = classRule || horn;
		m_numInstances = instances.numInstances();
		m_counterInstances = new ArrayList(m_numInstances);
		Enumeration enu = instances.enumerateInstances();
		while (enu.hasMoreElements()) {
			m_counterInstances.add(enu.nextElement());
		}
	}

	/**
	 * Returns a shallow copy of this rule. The structured is copied but the
	 * literals themselves are not copied.
	 * 
	 * @return A copy of this Rule.
	 */
	public Object clone() {

		Object result = null;
		try {
			result = super.clone();
			/* Clone the body and the head. */
			((Rule) result).m_body = (Body) m_body.clone();
			((Rule) result).m_head = (Head) m_head.clone();
			/* Clone the set of counter-instances. */
			if (m_counterInstances != null) {
				((Rule) result).m_counterInstances = (ArrayList) m_counterInstances
						.clone();
			}
		} catch (Exception e) {
			/* An exception is not supposed to happen here. */
			e.printStackTrace();
			System.exit(0);
		}
		return result;
	}

	/**
	 * Test if an instance is a counter-instance of this rule.
	 * 
	 * @param instance
	 *            The instance to test.
	 * @return True if the instance is a counter-instance.
	 */
	public boolean counterInstance(Instance instance) {

		return ((m_body.counterInstance(instance) && m_head
				.counterInstance(instance)));
	}

	/**
	 * Update the number of counter-instances of this rule in the dataset. This
	 * method should be used is the rule does not store its counter-instances.
	 * 
	 * @param instances
	 *            The dataset.
	 */
	public void upDate(Instances instances) {

		Enumeration enu = instances.enumerateInstances();
		m_numInstances = instances.numInstances();
		m_counter = 0;
		while (enu.hasMoreElements()) {
			if (this.counterInstance((Instance) enu.nextElement())) {
				m_counter++;
			}
		}
		m_head.upDate(instances);
		m_body.upDate(instances);
	}

	/**
	 * Get the confirmation value of this rule.
	 * 
	 * @return The confirmation.
	 */
	public double getConfirmation() {

		return m_confirmation;
	}

	/**
	 * Get the optimistic estimate of the confirmation obtained by refining this
	 * rule.
	 * 
	 * @return The optimistic estimate.
	 */
	public double getOptimistic() {

		return m_optimistic;
	}

	/*
	 * Get the expected number of counter-instances of this rule, calculated
	 * from the number of instances satisfying the body and the number of
	 * instances satisfying the negation of the head.
	 * 
	 * @return The expected number of counter-instances.
	 */
	public double getExpectedNumber() {

		return (double) m_body.getCounterInstancesNumber()
				* (double) m_head.getCounterInstancesNumber()
				/ (double) m_numInstances;
	}

	/**
	 * Get the expected frequency of counter-instances of this rule.
	 * 
	 * @return The expected frequency of counter-instances.
	 */
	public double getExpectedFrequency() {

		return getExpectedNumber() / (double) m_numInstances;
	}

	/**
	 * Get the observed number of counter-instances of this rule in the dataset.
	 * 
	 * @return The observed number of counter-instances.
	 */
	public int getObservedNumber() {

		if (m_counterInstances != null) {
			return m_counterInstances.size();
		} else {
			return m_counter;
		}
	}

	/**
	 * Get the observed frequency of counter-instances of this rule in the
	 * dataset.
	 * 
	 * @return The expected frequency of counter-instances.
	 */
	public double getObservedFrequency() {

		return (double) getObservedNumber() / (double) m_numInstances;
	}

	/**
	 * Get the rate of True Positive instances of this rule.
	 * 
	 * @return The TP-rate.
	 */
	public double getTPRate() {

		int tp = m_body.getCounterInstancesNumber() - getObservedNumber();
		int fn = m_numInstances - m_head.getCounterInstancesNumber() - tp;
		return ((double) tp / (double) (tp + fn));
	}

	/**
	 * Get the rate of False Positive instances of this rule.
	 * 
	 * @return The FP-rate.
	 */
	public double getFPRate() {

		int fp = getObservedNumber();
		int tn = m_head.getCounterInstancesNumber() - fp;
		return ((double) fp / (double) (fp + tn));
	}

	/**
	 * Calculate the confirmation of this rule.
	 */
	public void calculateConfirmation() {

		double expected = getExpectedFrequency();
		double observed = getObservedFrequency();
		if ((expected == 0) || (expected == 1)) {
			m_confirmation = 0;
		} else {
			m_confirmation = (expected - observed)
					/ (Math.sqrt(expected) - expected);
		}
	}

	/**
	 * Calculate the optimistic estimate of this rule.
	 */
	public void calculateOptimistic() {

		int counterInstances = this.getObservedNumber();
		int body = m_body.getCounterInstancesNumber();
		int notHead = m_head.getCounterInstancesNumber();
		int n = m_numInstances;
		double expectedOptimistic;
		/* optimistic expected number of counter-instances */
		if (counterInstances <= body - notHead) {
			expectedOptimistic = (double) (notHead * (body - counterInstances))
					/ (double) (n * n);
		} else if (counterInstances <= notHead - body) {
			expectedOptimistic = (double) (body * (notHead - counterInstances))
					/ (double) (n * n);
		} else {
			expectedOptimistic = (double) ((notHead + body - counterInstances) * (notHead
					+ body - counterInstances))
					/ (double) (4 * n * n);
		}
		if ((expectedOptimistic == 0) || (expectedOptimistic == 1)) {
			m_optimistic = 0;
		} else {
			m_optimistic = expectedOptimistic
					/ (Math.sqrt(expectedOptimistic) - expectedOptimistic);
		}
	}

	/**
	 * Test if this rule is empty.
	 * 
	 * @return True if it is the empty rule.
	 */
	public boolean isEmpty() {

		return (m_head.isEmpty() && m_body.isEmpty());
	}

	/**
	 * Give the number of literals in this rule.
	 * 
	 * @return The number of literals.
	 */
	public int numLiterals() {

		return m_body.numLiterals() + m_head.numLiterals();
	}

	/**
	 * Add a literal to the body of the rule.
	 * 
	 * @param newLit
	 *            The literal to add.
	 * @return The rule obtained by adding the literal, null if the literal can
	 *         not be added because of the constraints on the rule.
	 */
	private Rule addTermToBody(Literal newLit) {

		if (!m_negBody
				&& newLit.negative()
				|| (m_classRule && newLit.getPredicate().isClass())
				|| (newLit instanceof IndividualLiteral
						&& (((IndividualLiteral) newLit).getType() - m_body
								.getType()) > 1 && (((IndividualLiteral) newLit)
						.getType() - m_head.getType()) > 1)) {
			return null;
		} else {
			Rule result = (Rule) this.clone();
			result.m_body.addElement(newLit);
			/* Update the counter-instances. */
			if (m_counterInstances != null) {
				for (int i = result.m_counterInstances.size() - 1; i >= 0; i--) {
					Instance current = (Instance) result.m_counterInstances
							.get(i);
					if (!result.m_body.canKeep(current, newLit)) {
						result.m_counterInstances.remove(i);
					}
				}
			}
			return result;
		}
	}

	/**
	 * Add a literal to the head of the rule.
	 * 
	 * @param newLit
	 *            The literal to add.
	 * @return The rule obtained by adding the literal, null if the literal can
	 *         not be added because of the constraints on the rule.
	 */
	private Rule addTermToHead(Literal newLit) {
		if ((!m_negHead && newLit.negative())
				|| (m_classRule && !newLit.getPredicate().isClass())
				|| (m_singleHead && !m_head.isEmpty())
				|| (newLit instanceof IndividualLiteral && ((IndividualLiteral) newLit)
						.getType() != IndividualLiteral.INDIVIDUAL_PROPERTY)) {
			return null;
		} else {
			Rule result = (Rule) this.clone();
			result.m_head.addElement(newLit);
			/* Update counter-instances. */
			if (m_counterInstances != null) {
				for (int i = result.m_counterInstances.size() - 1; i >= 0; i--) {
					Instance current = (Instance) result.m_counterInstances
							.get(i);
					if (!result.m_head.canKeep(current, newLit)) {
						result.m_counterInstances.remove(i);
					}
				}
			}
			return result;
		}
	}

	/**
	 * Refine a rule by adding a range of literals of a predicate, either to the
	 * head or to the body of the rule.
	 * 
	 * @param pred
	 *            The predicate to consider.
	 * @param firstIndex
	 *            The index of the first literal of the predicate to add.
	 * @param lastIndex
	 *            The index of the last literal of the predicate to add.
	 * @param addTobody
	 *            True if the literals should be added to the body.
	 * @param addToHead
	 *            True if the literals should be added to the head.
	 * @return A list of rules obtained by refinement.
	 */
	private SimpleLinkedList refine(Predicate pred, int firstIndex,
			int lastIndex, boolean addToBody, boolean addToHead) {

		SimpleLinkedList result = new SimpleLinkedList();
		Literal currentLit;
		Literal negation;
		Rule refinement;
		for (int i = firstIndex; i < lastIndex; i++) {
			currentLit = pred.getLiteral(i);
			if (addToBody) {
				refinement = addTermToBody(currentLit);
				if (refinement != null) {
					result.add(refinement);
				}
			}
			if (addToHead) {
				refinement = addTermToHead(currentLit);
				if (refinement != null) {
					result.add(refinement);
				}
			}
			negation = currentLit.getNegation();
			if (negation != null) {
				if (addToBody) {
					refinement = addTermToBody(negation);
					if (refinement != null) {
						result.add(refinement);
					}
				}
				if (addToHead) {
					refinement = addTermToHead(negation);
					if (refinement != null) {
						result.add(refinement);
					}
				}
			}
		}
		return result;
	}

	/**
	 * Refine a rule by adding literal from a set of predictes.
	 * 
	 * @param predicates
	 *            The predicates available.
	 * @return The list of the children obtained by refining the rule.
	 */
	public SimpleLinkedList refine(ArrayList predicates) {

		SimpleLinkedList result = new SimpleLinkedList();
		Predicate currentPred;
		boolean addToBody;
		boolean addToHead;

		if (this.numLiterals() == m_maxLiterals) {
			return result;
		}

		if (this.isEmpty()) {
			/* Literals can be added on both sides of the rule. */
			for (int i = 0; i < predicates.size(); i++) {
				currentPred = (Predicate) predicates.get(i);
				result.addAll(refine(currentPred, 0, currentPred.numLiterals(),
						true, true));
			}
		} else if (m_body.isEmpty() || m_head.isEmpty()) {
			/* Literals can be added to the empty side only. */
			LiteralSet side;
			Literal last;
			if (m_body.isEmpty()) {
				side = m_head;
				addToBody = true;
				addToHead = false;
			} else { // m_head.isEmpty()
				side = m_body;
				addToBody = false;
				addToHead = true;
			}
			last = side.getLastLiteral();
			currentPred = last.getPredicate();
			if (m_repeatPredicate) {
				result.addAll(refine(currentPred,
						currentPred.indexOf(last) + 1,
						currentPred.numLiterals(), addToBody, addToHead));
			}
			for (int i = predicates.indexOf(currentPred) + 1; i < predicates
					.size(); i++) {
				currentPred = (Predicate) predicates.get(i);
				result.addAll(refine(currentPred, 0, currentPred.numLiterals(),
						addToBody, addToHead));
			}
		} else {
			Literal lastLitBody = m_body.getLastLiteral();
			Literal lastLitHead = m_head.getLastLiteral();
			Predicate lastPredBody = lastLitBody.getPredicate();
			Predicate lastPredHead = lastLitHead.getPredicate();
			int lastLitBodyIndex = lastPredBody.indexOf(lastLitBody);
			int lastLitHeadIndex = lastPredHead.indexOf(lastLitHead);
			int lastPredBodyIndex = predicates.indexOf(lastPredBody);
			int lastPredHeadIndex = predicates.indexOf(lastPredHead);
			Predicate inferiorPred;
			Predicate superiorPred;
			int inferiorLit;
			int superiorLit;
			addToBody = (m_head.numLiterals() == 1 && (lastPredBodyIndex < lastPredHeadIndex || (lastPredBodyIndex == lastPredHeadIndex && lastLitBodyIndex < lastLitHeadIndex)));
			addToHead = (m_body.numLiterals() == 1 && (lastPredHeadIndex < lastPredBodyIndex || (lastPredHeadIndex == lastPredBodyIndex && lastLitHeadIndex < lastLitBodyIndex)));
			if (addToBody || addToHead) {
				/* Add literals in the gap between the body and the head. */
				if (addToBody) {
					inferiorPred = lastPredBody;
					inferiorLit = lastLitBodyIndex;
					superiorPred = lastPredHead;
					superiorLit = lastLitHeadIndex;
				} else { // addToHead
					inferiorPred = lastPredHead;
					inferiorLit = lastLitHeadIndex;
					superiorPred = lastPredBody;
					superiorLit = lastLitBodyIndex;
				}
				if (predicates.indexOf(inferiorPred) < predicates
						.indexOf(superiorPred)) {
					if (m_repeatPredicate) {
						result.addAll(refine(inferiorPred, inferiorLit + 1,
								inferiorPred.numLiterals(), addToBody,
								addToHead));
					}
					for (int j = predicates.indexOf(inferiorPred) + 1; j < predicates
							.indexOf(superiorPred); j++) {
						currentPred = (Predicate) predicates.get(j);
						result.addAll(refine(currentPred, 0,
								currentPred.numLiterals(), addToBody, addToHead));
					}
					if (m_repeatPredicate) {
						result.addAll(refine(superiorPred, 0, superiorLit,
								addToBody, addToHead));
					}
				} else {
					// ((inferiorPred.getIndex() == superiorPred.getIndex())
					// && (inferiorLit < superiorLit))
					if (m_repeatPredicate) {
						result.addAll(refine(inferiorPred, inferiorLit + 1,
								superiorLit, addToBody, addToHead));
					}
				}
			}
			/* Add other literals. */
			if (predicates.indexOf(lastPredBody) > predicates
					.indexOf(lastPredHead)) {
				superiorPred = lastPredBody;
				superiorLit = lastPredBody.indexOf(lastLitBody);
			} else if (predicates.indexOf(lastPredBody) < predicates
					.indexOf(lastPredHead)) {
				superiorPred = lastPredHead;
				superiorLit = lastPredHead.indexOf(lastLitHead);
			} else {
				superiorPred = lastPredBody;
				if (lastLitBodyIndex > lastLitHeadIndex) {
					superiorLit = lastPredBody.indexOf(lastLitBody);
				} else {
					superiorLit = lastPredHead.indexOf(lastLitHead);
				}
			}
			if (m_repeatPredicate) {
				result.addAll(refine(superiorPred, superiorLit + 1,
						superiorPred.numLiterals(), true, true));
			}
			for (int j = predicates.indexOf(superiorPred) + 1; j < predicates
					.size(); j++) {
				currentPred = (Predicate) predicates.get(j);
				result.addAll(refine(currentPred, 0, currentPred.numLiterals(),
						true, true));
			}
		}
		return result;
	}

	/**
	 * Test if this rule subsumes another rule.
	 * 
	 * @param otherRule
	 *            The other rule.
	 * @return True if the other rule is subsumed.
	 */
	public boolean subsumes(Rule otherRule) {

		if (this.numLiterals() > otherRule.numLiterals()) {
			return false;
		}
		return (m_body.isIncludedIn(otherRule) && m_head
				.isIncludedIn(otherRule));
	}

	/**
	 * Test if this rule and another rule correspond to the same clause.
	 * 
	 * @param otherRule
	 *            The other rule.
	 * @return True if both rules correspond to the same clause.
	 */
	public boolean sameClauseAs(Rule otherRule) {

		return (this.numLiterals() == otherRule.numLiterals() && this
				.subsumes(otherRule));
	}

	/**
	 * Test if this rule is equivalent to another rule.
	 * 
	 * @param otherRule
	 *            The other rule.
	 * @return True if both rules are equivalent.
	 */
	public boolean equivalentTo(Rule otherRule) {

		return (this.numLiterals() == otherRule.numLiterals()
				&& m_head.negationIncludedIn(otherRule.m_body) && m_body
					.negationIncludedIn(otherRule.m_head));
	}

	/**
	 * Test if the body of the rule contains a literal.
	 * 
	 * @param lit
	 *            The literal to look for.
	 * @return True if the literal is contained in the body of the rule.
	 */
	public boolean bodyContains(Literal lit) {

		return m_body.contains(lit);
	}

	/**
	 * Test if the head of the rule contains a literal.
	 * 
	 * @param lit
	 *            The literal to look for.
	 * @return True if the literal is contained in the head of the rule.
	 */
	public boolean headContains(Literal lit) {

		return m_head.contains(lit);
	}

	/**
	 * Test if this rule is over the frequency threshold.
	 * 
	 * @param minFrequency
	 *            The frequency threshold.
	 * @return True if the rule is over the threshold.
	 */
	public boolean overFrequencyThreshold(double minFrequency) {

		return (m_body.overFrequencyThreshold(minFrequency) && m_head
				.overFrequencyThreshold(minFrequency));
	}

	/**
	 * Test if the body of the rule is true.
	 * 
	 * @return True if the body is always satisfied.
	 */
	public boolean hasTrueBody() {

		return (!m_body.isEmpty() && m_body.hasMaxCounterInstances());
	}

	/**
	 * Test if the head of the rule is false.
	 * 
	 * @return True if the body is never satisfied.
	 */
	public boolean hasFalseHead() {

		return (!m_head.isEmpty() && m_head.hasMaxCounterInstances());
	}

	/**
	 * Return a String giving the confirmation and optimistic estimate of this
	 * rule.
	 * 
	 * @return A String with the values of the rule.
	 */
	public String valuesToString() {

		StringBuffer text = new StringBuffer();
		DecimalFormat decimalFormat = new DecimalFormat("0.000000");
		text.append(decimalFormat.format(getConfirmation()));
		text.append(" ");
		text.append(decimalFormat.format(getObservedFrequency()));
		return text.toString();
	}

	/**
	 * Return a String giving the TP-rate and FP-rate of this rule.
	 * 
	 * @return A String with the values of the rule.
	 */
	public String rocToString() {

		StringBuffer text = new StringBuffer();
		DecimalFormat decimalFormat = new DecimalFormat("0.000000");
		text.append(decimalFormat.format(getConfirmation()));
		text.append(" ");
		text.append(decimalFormat.format(getTPRate()));
		text.append(" ");
		text.append(decimalFormat.format(getFPRate()));
		return text.toString();
	}

	/**
	 * Retrun a String for this rule.
	 * 
	 * @return The String describing this rule.
	 */
	public String toString() {

		StringBuffer text = new StringBuffer();
		text.append(m_body.toString());
		text.append(" ==> ");
		text.append(m_head.toString());
		return text.toString();
	}

	/**
	 * Comparator used to compare two rules according to their confirmation
	 * value.
	 */
	public static Comparator confirmationComparator = new Comparator() {

		public int compare(Object o1, Object o2) {

			Rule r1 = (Rule) o1;
			Rule r2 = (Rule) o2;
			double conf1 = r1.getConfirmation();
			double conf2 = r2.getConfirmation();
			if (conf1 > conf2) {
				return -1;
			} else if (conf1 < conf2) {
				return 1;
			} else {
				return 0;
			}
		}
	};

	/**
	 * Comparator used to compare two rules according to their observed number
	 * of counter-instances.
	 */
	public static Comparator observedComparator = new Comparator() {

		public int compare(Object o1, Object o2) {

			Rule r1 = (Rule) o1;
			Rule r2 = (Rule) o2;
			double obs1 = r1.getObservedFrequency();
			double obs2 = r2.getObservedFrequency();
			if (obs1 < obs2) {
				return -1;
			} else if (obs1 > obs2) {
				return 1;
			} else {
				return 0;
			}
		}
	};

	/**
	 * Comparator used to compare two rules according to their optimistic
	 * estimate.
	 */
	public static Comparator optimisticComparator = new Comparator() {

		public int compare(Object o1, Object o2) {

			Rule r1 = (Rule) o1;
			Rule r2 = (Rule) o2;
			double opt1 = r1.getOptimistic();
			double opt2 = r2.getOptimistic();
			if (opt1 > opt2) {
				return -1;
			} else if (opt1 < opt2) {
				return 1;
			} else {
				return 0;
			}
		}
	};

	/**
	 * Comparator used to compare two rules according to their confirmation and
	 * then their observed number of counter-instances.
	 */
	public static Comparator confirmationThenObservedComparator = new Comparator() {
		public int compare(Object o1, Object o2) {

			int confirmationComparison = confirmationComparator.compare(o1, o2);
			if (confirmationComparison != 0) {
				return confirmationComparison;
			} else {
				return observedComparator.compare(o1, o2);
			}
		}
	};

	/**
	 * Comparator used to compare two rules according to their optimistic
	 * estimate and then their observed number of counter-instances.
	 */
	public static Comparator optimisticThenObservedComparator = new Comparator() {
		public int compare(Object o1, Object o2) {
			int optimisticComparison = optimisticComparator.compare(o1, o2);
			if (optimisticComparison != 0) {
				return optimisticComparison;
			} else {
				return observedComparator.compare(o1, o2);
			}
		}
	};

	/**
	 * Returns the revision string.
	 * 
	 * @return the revision
	 */
	public String getRevision() {
		return RevisionUtils.extract("$Revision: 1.7 $");
	}
}
